Programmable logic devices such as field programmable gate arrays (FPGAs) are typically configured by downloading a configuration bitstream into a device's configuration memory. This configuration memory may be either a non-volatile memory such as FLASH or a volatile memory such as SRAM. For a variety of reasons including speed of operation, SRAM-based FPGAs currently dominate the programmable logic device market. As SRAM-based FPGAs continue to grow in complexity, the corresponding amount of SRAM needed to store the configuration data must grow as well. A conventional external non-volatile memory used to boot the configuration data into an SRAM-based FPGA is a Programmable Read Only Memory (PROM). The configuration bitstream from the external boot memory is typically shifted in a serial fashion. These external memories are often relatively expensive such that a compression scheme is desirable so that the configuration data may be stored in smaller (and hence less expensive) external boot memories. There are popular generic compression schemes, such as the Lempel-Ziv-Welch (LZW) algorithm, that may be used to compress configuration data. However, the implementation of the LZW algorithm is complex and resource-intensive. Thus, programmable logic devices such as FPGAs receiving LZW-compressed configuration bitstreams devote a considerable amount of die space to the corresponding configuration logic that implements the LZW decompression. Configuration bitstreams may also be compressed based upon the statistical distribution of data words within the bitstreams such as employed in Huffman encoding/decoding techniques. However, the implementation of Huffman decoding for programmable logic devices typically involves the use of external decoders and associated memories. The need for these additional components for Huffman-based compression schemes increases costs and complexity.
Accordingly, there is need in the art for more efficient configuration bitstream compression techniques.